In a network system, the resources (e.g., routers, switches, bandwidth, etc.) are finite in quantity. When the flow of data packets through the system is high, congestion can occur.
“Jitter” can be defined as the difference in time between when a data packet is ideally transmitted and the time at which the data packet is actually transmitted. “Burstiness” refers to the sending of data packets in bursts; that is, a number of data packets are sent at the same time or back-to-back over a short time interval, followed by an interval of significantly less activity. It is desirable to minimize jitter and burstiness by controlling traffic in a system.
One means for controlling or regulating traffic in a system is known as traffic shaping. A shaper delays excess traffic using a queuing mechanism to hold and delay packets. One type of queuing mechanism is commonly known as a token bucket mechanism. Speaking metaphorically, tokens are put into the bucket at a certain rate. The bucket has a specified capacity of tokens. Each token represents permission to transmit a certain number of bits. To send a data packet of a certain size, a sufficient number of tokens must be in the bucket. If there are not enough tokens in the bucket, the data packet is buffered until enough tokens are accumulated. When the data packet is sent, the number of tokens corresponding to the size of the packet is subtracted from the bucket. In essence, a token bucket is a counter that is increased by one count in each update interval, then decreased by one or more counts when a data packet is sent.
Consider a multi-level system. For simplicity, a three-level system is described, in which the nodes at the highest (downstream) level are referred to as ports, the nodes at the middle level are referred to as groups, and the nodes at the lowest (upstream) level are referred to as queues. Groups aggregate traffic from some number of queues, and ports aggregate traffic from some number of groups. The ports are coupled to a shared link (e.g., an optical cable or the like). On the shared link, there is a buffer for holding the traffic received from the ports. A token bucket is typically associated with each node in this system.
According to the prior art, the token buckets are updated sequentially (in series); that is, a token is added to a bucket at a queue node, then to another bucket at another queue node, and so on until all of the queue nodes are updated. Then a token is added to a bucket at a group node, then to another bucket at another group node, and so on until all of the group nodes are updated. The process is similarly repeated for the port nodes. Once the port nodes are updated, the update process returns to the queue nodes and is repeated. Serial or sequential updating is used instead of parallel updating because serial updating utilizes less complex control logic than parallel updating.
To send traffic, a node of the system is chosen according to some type of scheduling scheme (e.g., a round robin scheme) to determine whether the node is eligible for sending traffic to its downstream node. Each node is chosen in turn according to the scheduling scheme. Eligibility of a node is established by determining whether the node has enough tokens to allow a data packet to be sent, and whether there is a data packet to be sent. A port node can be considered an eligible candidate when it and any of its associated group or queue nodes is eligible. Similarly, a group node can be considered eligible when it and any of its associated queue nodes is eligible.
The update scheme described above helps smooth traffic through a system by buffering excess bursts as traffic enters the system (e.g., at the queue nodes). However, a problem with this update scheme is that it results in a troublesome degree of burstiness at the highest (e.g., port) level. As mentioned, each port aggregates traffic from a number of groups and queues, and each port is coupled to the shared link. Generally speaking, each port is almost always, if not always, sending traffic to the shared link at the maximum defined burst size. As such, the buffer downstream of the ports must be large enough to hold the maximum burst size. It is desirable to reduce the size of the downstream buffer; however, this is problematic unless the burst size at the ports is also reduced.
Accordingly, a device and/or method that can reduce burst size at high (e.g., port) level nodes in a network system is desirable. The present invention provides a novel solution to this and related problems.